1. Field of the Invention
The present invention relates generally to network routing, and more specifically to multipath muting control for connection-oriented networks such as asynchronous transfer mode (ATM) networks using progressive or originating control protocols.
2. Description of the Related Art
According to prior art routing protocols, as discussed in a paper "VC Routing Proposal", IETF Internet Draft, March 1993, R. Coltun and M. Sosa, when a virtual connection is established between a source and a destination node through an ATM network, the source node determines the entire path to the destination node and sends out an out-of-band signaling packet to an intermediate node, containing a full description of this path, including all node identifiers and possibly output port identifiers. The intermediate node forwards the packet by finding an output port identifier that corresponds to their node identifier, as well as the next node identifier, from the source route included in the signaling packet. Connection setup packets are transmitted from the source node through a pre-established virtual connection used for all signaling packets through a particular output port. Each connection setup packet contains a record route, i.e., a list of the node IDs of all nodes in the virtual connection through which the last connection setup packet has been traversed. When progressive routing is allowed, the route record is used to detect and avoid looping conditions, i.e., the conditions in which a call encounters the same node two or more times in a route path. The routing protocol for connection setup packets is based on a link-state protocol. Specifically, every source node and every intermediate node capable of rerouting obtain a map of the network topology, including the presence of all links, together with a link cost that indicates the desirability of using that link. Paths are compared to each other and determined according to their total costs, equal to the sum of the link costs for all of the links comprising a path. The link costs are updated dynamically with new link costs being broadcasted to all source nodes and all intermediate nodes capable of rerouting from time to time. All source nodes and all intermediate nodes capable of rerouting use their maps of the network topology to compute routing tables, which list one or more source routes for every possible destination address. The routing tables are used to choose source routes for connection setup packets, based on the destination address and QOS (quality of service) classes. The routing tables are updated when necessary after receiving new link cost updates.
According to the CCITT Recommendation I. 371 for the ATM standards, in-band cells are forwarded along the connection after a virtual connection has been set up by using virtual connection identifiers (VCIs) in the cell headers and forwarding tables at each node. At each node, the forwarding table includes a complete list of VCs crossing that node, including the input port ID and VCI for each connection, as well as the corresponding output port ID and VCI for the same connection. When an in-band cell arrives at a certain input port with a certain VCI, the forwarding table can be used to find the corresponding output port and VCI. After changing the VCI in the cell header to the new value, the cell is forwarded to the output port and thus forwarded toward the next node for that connection. After a virtual connection has been established, each intermediate node along the connection should include corresponding entries in its forwarding table. In order to support quality-of-service classes, each node much check to see if required resources are available for a link to the next hop. If the required resources are not available, then the connection is blocked at this link. In this case, either a new path should be chosen or the connection setup process fails and no connection is established.
Prior art multipath routing protocols are broadly classified into two categories: progressive routing protocols and originating routing protocols. The progressive routing control allows intermediate nodes to reroute the connection when it is blocked while with the originating, control rerouting decision is only made at the source node. The primary advantage of progressive routing is the ability to provide fast connection setup, particularly when the propagation delay across the network an be large. The disadvantage of progressive routing include the use of suboptimal alternate paths after connection is blocked and the possibility of looping and crankback, which require complicated signaling and processing in order to detect and avoid setting up paths with loops. The primary advantage of originating control is the ability to provide the best alternate paths, or the paths with the least total cost if link-state protocols are used. The disadvantage of originating control is the possibility of long connection setup times when propagation delay is significant.